
import java.util.*;
public class test {
    // kotori和气球
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // n 种气球,每种"无数"个
        int n = in.nextInt();
        // 一排 m 个
        int m = in.nextInt();
        long nn = n - 1;
        long sum = n;
        for(int i = 2;i <= m;i++){
            sum *= nn;
            sum %= 109;
        }
        System.out.println(sum % 109);
    }

    // 走迷宫
    public static int n;
    public static int m;
    public static int min;
    public static int x1,y1,x2,y2;
    public static boolean flg;
    public static boolean[][] floor;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};
    public static int INF = 0x3f3f3f3f;
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        min = INF;
        n = in.nextInt();
        m = in.nextInt();
        x1 = in.nextInt();
        y1 = in.nextInt();
        x2 = in.nextInt();
        y2 = in.nextInt();
        floor = new boolean[n + 5][m + 5];
        for(int i = 1;i <= n;i++){
            String s = in.next();
            char[] chars = s.toCharArray();
            for(int j = 0;j < m;j++){
                // 为障碍物,则标记,否则无视
                if(chars[j] == '*'){
                    floor[i][j + 1] = true;
                }
            }
        }
        int[][] dp = new int[n + 5][m + 5];
        for(int i = 0;i <= n;i++){
            Arrays.fill(dp[i],INF);
        }
        dp[x1][y1] = 0;
        int i = x1;int j = y1;
        for(i = 1;i <= n;i++){
            for(j = 1;j <= m;j++){
                for(int k = 0;k < 4;k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x > 0 && x <= n && y > 0 && y <= m && !floor[x][y]){
                        dp[x][y] = Math.min(dp[x][y],dp[i][ j] + 1);
                    }
                }
            }
            for(j = m;j >= 1;j--){
                for(int k = 0;k < 4;k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x > 0 && x <= n && y > 0 && y <= m && !floor[x][y]){
                        dp[x][y] = Math.min(dp[x][y],dp[i][ j] + 1);
                    }
                }
            }
        }
        for(i = n;i >= 1;i--){
            for(j = 1;j <= m;j++){
                for(int k = 0;k < 4;k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x > 0 && x <= n && y > 0 && y <= m && !floor[x][y]){
                        dp[x][y] = Math.min(dp[x][y],dp[i][ j] + 1);
                    }
                }
            }
            for(j = m;j >= 1;j--){
                for(int k = 0;k < 4;k++){
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x > 0 && x <= n && y > 0 && y <= m && !floor[x][y]){
                        dp[x][y] = Math.min(dp[x][y],dp[i][ j] + 1);
                    }
                }
            }
        }
        System.out.println(dp[x2][y2] == INF ? -1 : dp[x2][y2]);
    }
    // 主持人调度(二)
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // 2
        // [1,3] [2,4]
        int sum = 1;
        int len = startEnd.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparing(a -> (a[0])));
        // 用于保存每一个主持人"上一次演讲"的最早结束时间
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        for(int i = 0;i < len;i++){
            queue.offer(startEnd[i]);
        }
        queue1.offer(queue.poll()[1]);
        while (!queue.isEmpty()) {
            int[] nums = queue.poll();
            int start = nums[0];
            int end = nums[1];
            // 最早结束也赶不上
            if(queue1.peek() > start){
                queue1.offer(end);
                sum++;
            }else {
                queue1.poll();
                queue1.offer(end);
            }
        }
        return sum;
    }
}
